package com.dhu.graph.basic.paths.impls;

import com.dhu.graph.basic.GraphImpls.DiGraph;
import com.dhu.graph.basic.paths.Paths;
import com.dhu.graph.utils.LinkStack;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-03
 * @ Description：有向图的寻找路径
 * @ Modified By：
 * @ Version:
 */
public class DepthFirstDirectedPaths implements Paths {
    private boolean[] marked;
    private Integer[] pathTo;   //跟无向图中相同，path[w] = v 表示 v指向w
    private final int s;
    public DepthFirstDirectedPaths(DiGraph G, int s){
        this.s = s;
        this.marked = new boolean[G.V()];
        dfs(G, s);
    }
    private void dfs(DiGraph G, int v) {
        marked[v] = true;
        for (Integer w : G.adj(v)) {
            if (!marked(v)){
                pathTo[w] = v;
                dfs(G, w);
            }
        }
    }
    private boolean marked(int v){
        return marked[v];
    }

    /**
     * 由 s 指向v 的有向路径
     * @param v
     * @return
     */
    @Override
    public Iterable<Integer> pathsTo(int v) {
        if (!hasPathTo(v)) return null;
        LinkStack<Integer> stack = new LinkStack<>();
        for (int x = v; v != s; x = pathTo[x]){
            stack.push(x);
        }
        stack.push(s);
        return stack;
    }

    @Override
    public boolean hasPathTo(Integer v) {
        return marked[v];
    }
}
